% \documentclass{article}
% \usepackage{graphicx}
% 
% \setlength{\parskip}{\baselineskip}
% \setlength{\parindent}{0em}
% 
% \newcommand{\bigH}{\mathcal{H}}
% \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
% \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}


% \begin{document}

\section{Group formation}
%\includegraphics[keepaspectratio, scale=.5]{drawing.pdf}
Having rigorously considered the behavior of uniform-cost clusters, we would like to consider more general, hierarchical structures. In this section, we will analyze two clusters such that (1) each has a unique, fixed cost, and (2) there is some third fixed cost on intra-cluster edges.

Given two clusters, $C$ and $\hat{C}$, not connected to one another, what conditions will allow them to connect? For the purposes of this analysis, we will assume that both clusters are stable individually for their particular internal edge cost. This ensures that
neither will want to immediately drop any edge or add any internal edges. Let any edges that form between the two cluster have cost $\omega$. We would like to know for which $\omega$ any such edges would form.

The strategy to solve this problem is to find the highest value that can be gained from the addition of a connecting edge. Let the value of the most valuable edge between such two clusters be $\Psi$. So, if $\omega < \Psi$, the edge will form, and the pair of components is not stable.

We calculated the value of $\Psi$ for specific component pairs between structures whose internal utilities we had already cataloged, like stars, lines, rings, complete graphs, and hedgehogs. For every possible pair of these structures, with node-counts $n_1$ and $n_2$, we found the value of $\Psi$.

Relevant observations that narrow considerations and simplify calculations:

\begin{enumerate}
 \item Adding an edge that connecting $C$ and $\hat{C}$ has the same change in value for both nodes involved (Theorem \ref{equalvaluetheorem}).
\item The most valuable edge will be formed between the nodes with the highest value from being an endpoint, which happen to be, in the specific structures we consider, the nodes with the highest overall value (see Conjectures \ref{conjendpt1} and \ref{conjendpt2})
\begin{enumerate}
\item In rings and complete graphs, all nodes have the same value and thus are essentially equivalent
\item In a line, the node with highest value is the one in the center (for odd sizes; or of the center pair for even lines)
\item In stars, the node that has the highest value is the middle node
\item In 1-hedgehogs, any node that is not a tail ties for the highest value
\end{enumerate}
\end{enumerate}

In discussing each pair of structures, we will refer to the change in value from the addition of the edge between two highest-value nodes in two components of type $x$ and $y$ of size $n_1$ and $n_2$, respectively: $\deltav{x}{y}{n_1}{n_2}$, where $x$ and $y$ are symbols defined for each of the structures discussed. For example, \openbullet refers to a cycle, $\star$ refers to a star, and so on. We have cataloged, in the noted sections, the following two-cluster structures, represented by the indicated symbols:
\begin{center}
\begin{tabular}{c|ccccc}
  \toprule
  & Line $\wr$ & Star $\star$ & Ring \openbullet & 1-hedgehog $\hh$ & Complete $\bullet$ \\
  \midrule
  $\wr$ & \ref{line-line} & & & & \\
  $\star$ &  \ref{star-line} & \ref{star-star} & & & \\
  \openbullet & \ref{ring-line} & \ref{star-ring} &\ref{ring-ring} & & \\
  $\hh$ &\ref{1hh-line} & \ref{star-1hh} & \ref{1hh-ring} & \ref{1hh-1hh} & \\
  $\bullet$ & \ref{k-line} & \ref{k-k} & \ref{k-ring} & \ref{k-1hh} & \ref{k-k} \\
  \bottomrule
\end{tabular}
\end{center}

\subsection{Complete Graphs / Stars and Complete Graphs / Stars}

\subsubsection{Stars and Stars}
\label{star-star}
Let one star be size $n_1$ and the other be size $n_2$. The first star has center node $s$ and the second has center node $t$.

The change in value from the addition of the edge between $s$ and $t$ is:

$$ \deltav{\star}{\star}{n_1}{n_2} = \frac{n_1 - 1}{3} + \frac{(n_1 - 1)(n_2 - 1)}{4} + \frac{n_2 - 1}{3} + \frac{1}{2}$$

The first term comes from pairs between the leaves of the first star and $t$, which are all length three paths. The second term comes from pairs between the leaves of the first star and the leaves of the second star, which are all length four paths. The third term comes from pairs between $s$ and the leaves of the second star, and the fourth term is due to the pair between $s$ and $t$.

\subsubsection{Complete Graphs and Complete Graphs / Stars}
\label{k-k}

Since complete graphs behave the same as stars as far as connecting another component to them is concerned, we need only consider the stars-to-stars case.

The change in value due to connecting two complete graphs, then, is this function:

$$\deltav{\bullet}{\bullet}{n_1}{n_2} = \deltav{\bullet}{\star}{n_1}{n_2} = \deltav{\star}{\star}{n_1}{n_2}$$


%Let $n_1$ be the size of the star and $n_2$ be the size of the complete graph. 
%The highest value node in the star is the center node, and every node in the complete graph is identical. Let the center node of the star be $s$ and the connecting node of the complete graph be $t$.
%The change in utility due to the addition of the edge between these parts is made up of the following pieces:

%$$\frac{n_1 - 1}{3} + \frac{(n_1 - 1)(n_2 - 1)}{4} + \frac{n_2 - 1}{3} + \frac{1}{2}$$

%The first term comes from the pairs between every leaf of the star and $t$. These paths contain three nodes, and there are $(n_1 - 1)$ of them. The second term comes from the pairs between each leaf of the star and every non-$t$ node in the complete graph. These have four nodes, and there are $(n_1 - 1)(n_2 - 1)$ of them. The third term comes from pairs between every non-$t$ node in the complete graph and $s$. The last term comes from the pair between $s$ and $t$. This accounts for all the value gained by $s$ and $t$. Each also pays a cost $\omega$ for this edge. So, if $\omega$ is greater than the sum of these terms, the edge will not form.


\subsection{Complete Graphs / Stars and 1-Hedgehogs}

\subsubsection{Complete Graphs and 1-Hedgehogs}
\label{k-1hh}

Since complete graphs behave the same as stars as far as connecting another component to them is concerned, we need only consider the stars-to-hedgehogs case.

$$\deltav{\bullet}{\hh}{n_1}{n_2} = \deltav{\star}{\hh}{n_1}{n_2}$$

\subsubsection{Stars and 1-Hedgehogs}
\label{star-1hh}

Let $n_1$ be the size of the star, and $n_2$ be the size of the hedgehog. The connecting node on the star is $s$. Let the  connecting node on the 1-hedgehog be $t$. Since a hedgehog of size $n_2$ is just a complete graph of size $n_2/2$ with $n_2/2$ extra tail nodes, the value gained is the same as the value for stars of $n_1$ and complete graphs of $n_2/2$  (\ref{star-star}) , but with these extra terms:


$$\deltav{\star}{\hh}{n_1}{n_2} = \deltav{\star}{\star}{n_1}{\frac{n_2}{2}} + \frac{(n_1-1)(\frac{n_2}{2} - 1)}{5} + \frac{n_1 - 1}{4} + \frac{\frac{n_2}{2} - 1}{4} + \frac{1}{3}$$

The first term is due to the pairs between the leaves of the star and the far tail nodes of the hedgehog. The second term is due to the pairs between the leaves of the star and the closer tail of the hedgehog. The third term is due to the pairs between $s$ and the far tails of the hedgehog. The fourth term is between $s$ and the close tail of the hedgehog.


\subsection{Complete Graphs / Stars and Lines}

\subsubsection{Lines and Complete Graphs}
\label{k-line}

Since complete graphs behave the same as stars as far as connecting another component to them is concerned, we need only consider the stars-to-lines (\ref{star-line}) case.

$$\deltav{\bullet}{\wr}{n_1}{n_2} = \deltav{\star}{\wr}{n_1}{n_2}$$


\subsubsection{Stars and Lines}
\label{star-line}

Let $n_1$ be the size of the star and $n_2$ be the length of the line. The most valuable node in the line is the middle one. If $n_2$ is even, the most valuable node is either of the middle two.

Using $\gamma$ as shorthand for $\frac{n_2+1}{2}$ and $\bigH(x)$ for the harmonic series beginning at 1, the change in value due to the connection between the center of the star $s$ and the middle of the line $t$ is the following:

$$\deltav{\star}{\wr}{n_1}{n_2} = (n_1-1)\left[\bigH \left( \ceil{\gamma} + 2 \right) + \bigH \left( \floor{\gamma} + 2 \right)  - \frac{10}{3}\right] + \bigH \left( \ceil{\gamma} + 1 \right) + \bigH \left( \floor{\gamma} + 1 \right) - \frac{5}{2}$$

The left side (the part multiplied by $n_1 - 1$) accounts for every pair involving the leaves of the star. Within this, the left harmonic series comes from the pairs proceeding down one side and the right harmonic series comes from the other side. These series are of the form $1 + 1/2 + 1/3 + \ldots + \frac{1}{\gamma + 1}$. Since the shortest path of this type is actually only size three, we need to subtract the $1 + 1/2$ out of both of these, and one of the $1/3$ terms (the path from a leaf to $t$ appears only once). This explains the $10/3$ term.

The right side of the expression accounts for every pair involving the center of the star $s$. The two harmonic series appear as with the leaves, but every path is one shorter. Here the shortest term we want to consider is 1/2, and only one of these, so we subtract $2 + 1/2$, or $5/2$. 

The floors and ceilings allow the expression to work for both odd and even-length lines. If $n_2$ is odd, then $n_2 + 1$ is divisible by two, and $\floor{\gamma} = \ceil{\gamma}$. In this case, the number of nodes from the middle node to either side of the line is $\gamma$. In the case that $n_2$ is even, $\floor{\gamma}$ and $\ceil{\gamma}$ will differ by 1, since one side of the path is one larger than the other.



\subsection{Complete Graphs / Stars and Rings}
\subsubsection{Complete Graphs and Rings}
\label{k-ring}

Since complete graphs behave the same as stars as far as connecting another component to them is concerned, we need only consider the stars-to-rings (\ref{star-ring}) case.

$$\deltav{\bullet}{\openbullet}{n_1}{n_2} = \deltav{\star}{\openbullet}{n_1}{n_2}$$


\subsubsection{Stars and Rings}
\label{star-ring}

Let $n_1$ be the size of the star and $n_2$ be the size of the ring. This structure is very similar to the star and line structure when $n_2$ is odd, since the pair of nodes directly across the ring from $t$ may as well be disconnected as far as the change in value is concerned.

When $n_2$ is odd, the change in value is identical to the change in value for a star and a line of the same size (\ref{star-line}) .

$$\deltav{\star}{\openbullet}{n_1}{n_2} = \deltav{\star}{\wr}{n_1}{n_2}$$

When $n_2$ is even, the change in value contains the change in value of a star and a line of size $n_2 - 1$. It also has the following terms:

$$\deltav{\star}{\openbullet}{n_1}{n_2} = \deltav{\star}{\wr}{n_1}{n_2-1} + \frac{n_1 - 1}{n_2 + 2} + \frac{1}{n_1 + 1}$$

The first term is from all pairs involving leaves of the star and the node on the ring opposite $t$. There are duplicate paths for these pairs, so all the nodes in the ring and two of the star nodes ($s$ and the leaf) are involved. The second term is the value from the pair between $s$ and the opposite node.

\subsection{1-Hedgehogs and 1-Hedgehogs}
\label{1hh-1hh}

Except for the tail nodes of both components, this is the same as two complete graphs on $n_1/2$ and $n_2/2$ (\ref{k-k}). So, the change in value is the same as for that configuration with terms added:

$$\deltav{\hh}{\hh}{n_1}{n_2} = \deltav{\bullet}{\bullet}{\frac{n_1}{2}}{\frac{n_2}{2}} + \frac{(\frac{n_1}{2} - 1)(\frac{n_2}{2} - 1)}{4}$$


\subsection{1-Hedgehogs and Lines}
\label{1hh-line}

Let the line have $n_1$ nodes and the connection node $s$. Let the 1-hedgehog have $n_2$ nodes and the connection node $t$. When $n_1$ is odd, the change in value here is equivalent to the change in value for 1-hedgehogs and Rings (\ref{1hh-ring}).

$$\deltav{\wr}{\hh}{n_1}{n_2} = \deltav{\openbullet}{\hh}{n_1}{n_2}$$

When $n_1$ is even, we get the additional term

$$\deltav{\wr}{\hh}{n_1}{n_2} = \deltav{\openbullet}{\hh}{n_1}{n_2} + \frac{1}{n_1/2+1} + \frac{n_2/2}{n_1/2+2} + \frac{n_2/2 - 1}{n_1/2+3} $$

The first term after the $\deltav{\openbullet}{\hh}{n_1}{n_2}$ term, $\frac{1}{n_1/2+1}$, is the contribution from the path from the last node of the line to $t$. The second term quantifies the contributions from the paths from the last node of the line to all but one of the body nodes of the 
hedgehog as well as the close tail node. The last term refers to the contributions from the last node to the far tail nodes of the hedgehog.
\subsection{1-Hedgehogs and Rings}
\label{1hh-ring}

Let the ring have $n_1$ nodes and the connection node $s$. Let the 1-hedgehog have $n_2$ nodes and the connection node $t$. In a ring, all nodes are essentially the same, and $s$ can be any arbitrary node. When $n_1$ is odd, the change in value is

$$\deltav{\openbullet}{\hh}{n_1}{n_2} = 2\sum_{i=2}^{\ceil{\frac{n_1}{2}}-1} \left( \frac{1}{i+1} + \frac{n_2}{2(i+2)} + \frac{n_2 - 2}{2(i+3)}\right) + \left( \frac{1}{2} + \frac{n_2}{6} + \frac{n_2 - 2}{8}\right) $$

The summation summarizes the contributions from the paths involving nodes $i=2,...,n_2/2$ on either side of the ring. The first term in the sum refers to the path from $t$ to $i$; the second - from the body nodes and the close tail of the hedgehog to $i$; the third - from the far tails to $i$. The Additional 3 terms are analogues for connections to $s$.

When $n_1$ is even, we get some additional terms:

$$\deltav{\openbullet}{\hh}{n_1}{n_2} = \deltav{\openbullet}{\hh}{n_1-1}{n_2} + \frac{1}{n_1+1} + \frac{n_2}{2(n_1+2)} + \frac{n_2 - 2}{2(n_1+3)} $$

\subsection{Lines and Lines}
\label{line-line}

Let the lines have lengths $n_1$, and $n_2$. We will consider adding an edge between the centers of the lines.

\begin{eqnarray*}
\deltav{\wr}{\wr}{n_1}{n_2} = & & \frac{1}{2} + \sum_{i=2}^{\ceil{ \frac{n_1}{2} } } { \left( \frac{1}{i+1} \right) }+ \sum_{i=2}^{\floor{\frac{n_1}{2}}}{\left(\frac{1}{i+1}\right)} \\
 & + &  \sum_{i=2}^{\ceil{\frac{n_2}{2}}}{\left(\frac{1}{i+1} + \sum_{j=2}^{\ceil{\frac{n_1}{2}}}{\left(\frac{1}{i+1}\right)}+ \sum_{j=2}^{\floor{\frac{n_1}{2}}}{\left(\frac{1}{i+1}\right)} \right)} \\
 & + & \sum_{i=2}^{\floor{\frac{n_2}{2}}}{\left(\frac{1}{i+1} + \sum_{j=2}^{\ceil{\frac{n_1}{2}}}{\left(\frac{1}{i+1}\right)}+ \sum_{j=2}^{\floor{\frac{n_1}{2}}}{\left(\frac{1}{i+1}\right)} \right)}
\end{eqnarray*}

 The first three terms come from paths that end at either $s$ or $t$. The last two sums cover all paths between the component when $n_1$ and $n_2$ are either even or odd.
\subsection{Rings and Lines}
\label{ring-line}

Let the ring be of size $n_1$ with the connection node $s$ and the line be of size $n_2$ with the connection node $t$. The change in value when $n_1$ is odd is equivalent to the the lines-to-lines (\ref{line-line}) case:

$$\deltav{\openbullet}{\wr}{n_1}{n_2} = \deltav{\wr}{\wr}{n_1}{n_2}$$

We need several additional terms to make that expression when $n_1$ is even:

$$\deltav{\openbullet}{\wr}{n_1}{n_2} = \deltav{\wr}{\wr}{n_1-1}{n_2} + \frac{2}{n_1 + 1} + \sum_{i=2}^{\floor{\frac{n_2}{2}}} {(\frac{1}{n_1+i})} + \sum_{i=2}^{\ceil{\frac{n_2}{2}}} {(\frac{1}{n_1+i})} $$

Once again, floors and ceilings allow us to express both even and odd $n_2$ cases.
\subsection{Rings and Rings}
\label{ring-ring}

Let one ring have $n_1$ nodes and connection node $s$. The other has $n_2$ nodes and connection node $t$. When both $n_1$ and $n_2$ are odd, the change in value is equivalent to the lines-to-lines (\ref{line-line}) case:

$$\deltav{\openbullet}{\openbullet}{n_1}{n_2} = \deltav{\wr}{\wr}{n_1}{n_2} $$

%$$\deltav{\openbullet}{\openbullet}{n_1}{n_2} = \frac{1}{2} + 2 \sum_{i=0}^{\floor{\frac{n_1}{2}}}{\sum_{i=1}^{\floor{\frac{n_1}{2}}}{\frac{2}{i+j+2}}}$$

%Its right. We know it is.

When both $n_1$ and $n_2$ are even, there are nodes opposite $s$ and $t$. Let these be $s'$ and $t'$. The pairs involving either $s'$ or $t'$ must be treated separately since they always have duplicate paths. The change in value still contains the odd-odd value change on $n_1-1$ and $n_2 - 1$ nodes, but it also has additional terms:

$$\deltav{\openbullet}{\openbullet}{n_1}{n_2} = \deltav{\openbullet}{\openbullet}{n_1-1}{n_2-1} + \frac{1}{n_1+1} + \frac{1}{n_2+1} + \frac{1}{n_1+n_2} + \sum_{i=2}^{\frac{n_2}{2}}{\frac{2}{n_1 + i}} + \sum_{i=2}^{\frac{n_1}{2}}{\frac{2}{n_2 + i}}$$

After the $\deltav{\openbullet}{\openbullet}{n_1-1}{n_2-1}$ term, the first term is from the pair between $s'$ and $t$. The next term is from the pair between $t'$ and $s$. Both of these have duplicate paths that involve all of the nodes on their respective rings. The third term comes from the pair between $s'$ and $t'$. The shortest paths between these pass through all the nodes of both components. The fourth term (the first summation) comes from paths from $s'$ to each of the non-$t$ and non-$t'$ nodes in the other component. There are $n_2 - 2$ such pairs, or $2 \cdot (\frac{n_2}{2} - 1)$, as given by the sum from 2 to $\frac{n_2}{2}$. Each of these includes all $n_1$ nodes in the first ring. The fifth term is symmetrical to the fourth.

When $n_1$ is even and $n_2$ is odd, the utility is the same as for an even cycle and a line (\ref{ring-line}):

$$ \deltav{\openbullet}{\openbullet}{n_1}{n_2} =  \deltav{\openbullet}{\wr}{n_1}{n_2}$$
%$$\deltav{\openbullet}{\openbullet}{n_1-1}{n_2} + \frac{1}{n_1+1} + \sum_{i=2}^{\ceil{\frac{n_2}{2}}}{\frac{2}{n_1 + i}}$$

%As before, after the $\deltav{\openbullet}{\openbullet}{n_1-1}{n_2}$ term, the first term comes from the pair between $s'$ and $t$. The sum comes from all pairs between $s'$ and the non-$t$ nodes of the second ring, as in the even-even case.


% \end{document}
